package com.gwcloud.leetcode.hot100;

import java.util.Stack;

/** 
* @ClassName   : Leetcode0739 
* @author      : ganwei 
* @date        : 2020年5月24日 
* @Description : 739. 每日温度 
*/
public class Leetcode0739 {
	/**
	 * -解题思路,暴力思路!!!!，有点慢，但是能提交成功。。。
	 */
    public int[] dailyTemperatures(int[] T) {
        int[] nums = new int[T.length];
    	for(int i = 0; i < T.length; i++) {
        	for(int j = i; j < T.length; j++) {
        		if(T[i] >= T[j]) {
        			nums[i] ++;
        			if(j == T.length-1) {
        				nums[i] = 0;
        			}
        		}else {
        			break;
        		}
        	}
        }
    	return nums;
    }
    
    /**
     * -栈的思路
     */
    public int[] dailyTemperatures_1(int[] T) {
    	Stack<Integer> stack = new Stack<>();
    	int[] nums = new int[T.length];
    	
    	for(int i = 0; i < T.length; i++) {
    		while(!stack.isEmpty() && T[i] > T[stack.peek()]) {
    			int pre = stack.pop();
    			nums[pre] = i - pre;
    		}
    		stack.add(i);
    	}
    	
    	return nums;
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	Leetcode0739 l0739 = new Leetcode0739();
    	int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
    	int[] nums = l0739.dailyTemperatures_1(temps);
    	for(int num : nums) {
    		System.out.print(num);
    		System.out.print(" ");
    	}
    }
}
